A combinational circuit with the capability of detecting the completion of its operation exhibits the very important advantage of data-dependent input to output delay. Thus, compared to conventional, fixed-delay counterparts, where the delay is either modeled through the use of a global, fixed frequency clock, or by using a fixed delay reference, if the circuit is without a clock, it is capable of operating without the constraint of a fixed, worst-case critical path. Instead, a clock-less circuit operates with a variable critical path based on the gates that are sensitized for a given input vector. This allows the circuits to operate with an average case delay, i.e. a delay proportional to the average case of a specific input data sample composed of a large collection of operational input vectors. This allows circuits with completion detection to have increased performance.
Circuits with completion detection possess three fundamental implementation requirements, i.e. a data encoding scheme, two-phase alternating NULL/DATA operation, and monotonic transitions at all of the circuit components. The data encoding scheme must contain: (i) a code word for an EMPTY or NULL or SPACER value, which typically designates an empty channel, i.e. data absent at a specific circuit portion, and (ii) VALID code words which represent the presence of binary signal values (e.g. “0” or “1” for a single bit value), which typically designates a full channel, i.e. data arrival of a particular value at a specific circuit portion. The two-phase operation is required to prevent data interference between the VALID and NULL code words. Thus, the typical operation of circuits with completion detection is to alternate between NULL and VALID code words at the inputs by observing an acknowledgement, synchronization signal, which is typically communicated by a sequential (state storing) circuit. This ensures that the VALID word is generated by reading the completion signal and is stored in a sequential register. Monotonic operation or monotonic transition implies that any circuit node during a VALID code word propagation is either rising or falling, and ultimately stabilizes to a high or a low voltage without any change in the direction based on circuit delays, gate switching order or hazards. The propagation of the NULL word is merely used to reset all the circuit nodes to their NULL state in order to ensure monotonic operation.
Thus, the typical mode of operation of a circuit with completion detection is the following. First, all of the circuit's nodes are reset to the NULL codeword by feeding NULL to the inputs. Next, a VALID code word is applied. Thus, based on the polarity of the gates, some nodes will be rising while others will be falling. After the VALID computation is complete, a new NULL word is introduced to clear all the circuit's nodes. The application of the NULL word achieves the opposite effect to the prior VALID codeword, i.e. if a node rose to high, now it will typically return to low, and vice versa. The most common encoding scheme for implementing circuits with completion detection is the Dual-Rail encoding scheme. The Dual-Rail encoding scheme encodes at least three values, i.e. NULL, VALID0 and VALID1 using two wires. Typically, NULL is encoded as the digital representation 00, whereas VALID0 and VALID1 are typically encoded as 10 and 01, respectively. In Dual-Rail conversion approaches, where negative polarity gates are allowed for the Dual-Rail implementation, NULL typically possesses two encodings, i.e. 00 or 11, based on the polarity of a node, positive or negative respectively.
There are three fundamental drawbacks with Dual-Rail encoded circuit implementations: (i) area overhead, (ii) power consumption overhead and (iii) cycle time overhead. The first drawback stems from the necessity to generate logic gates for both rails instead of just one, as in binary logic. The second drawback stems from the additional logic for the two rails and the two-phase operation. Both factors significantly increase the number of transitions for a circuit cycle. The third drawback stems from the two-phase operation, where the cycle time of the Dual-Rail circuit is the sum of the delay of the VALID propagation and the delay of the NULL propagation. The combined delay is potentially larger than that of a binary, i.e., un-encoded, circuit.
In view of the foregoing, it would be desirable to develop techniques to overcome shortcomings associated with prior art circuits incorporating completion detection.